package com.zrrd.zuo.class07;

import jdk.nashorn.internal.objects.annotations.Where;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author ywb
 * @Description:
 * @date 2023/3/31 16:47
 */
public class BinaryTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }
    //递归方式
    public static void f(Node head) {
        if (head == null) {
            return;
        }
        // 1
        f(head.left);
        // 2
        f(head.right);
        // 3
    }
    //非递归
    //先序
    /*
    * 先弹再压右压左
    * */
    public static void pre(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
    }
    /**
     *先向左压到头 再弹出 再走右
     */
    public static void in(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }

            }
        }
    }
    /**
     * 后续较简单实现 先序压入栈 再取出
     * */
    public static void pos(Node head){
        if(head != null){
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.add(head);
            while (!s1.isEmpty()){
                head = s1.pop();
                s2.push(head);
                System.out.print(head.value + " ");
                if (head.right != null) {
                    s1.push(head.right);
                }
                if (head.left != null) {
                    s1.push(head.left);
                }
            }
        }
    }
/**
 * 另一种方式 记住！！
 * */
    public static void pos2(Node h) {
        System.out.print("pos-order: ");
        if (h != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }
/**
 * 宽度优先
 * */
    public  static void level(Node head){
        if (head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.value + " ");
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        in(head);
        System.out.println("========");
        pos(head);
        System.out.println("========");
//        pos2(head);
//        System.out.println("========");
        level(head);
        System.out.println("========");
    }


}
